package practice;

import java.util.*;

public class Day42 {
    //LRU换存
    class LRUCache {
        class Node{
            int key;
            int val;
            Node prev;
            Node next;
            public Node() {}
            public Node(int key,int value) {
                this.key = key;
                this.val = value;
            }
        }
        Map<Integer,Node> map;
        Node head;
        Node tail;
        int n;
        int size;
        public LRUCache(int capacity) {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
            n = capacity;
            map = new HashMap<>();
        }

        public int get(int key) {
            Node node = map.getOrDefault(key,null);
            if(node == null) {
                return -1;
            }else {
                moveToHead(node);
                return node.val;
            }
        }

        public void put(int key, int value) {
            Node node = map.getOrDefault(key,null);
            if(node == null) {
                //新建
                Node cur = new Node(key,value);
                map.put(key,cur);
                size++;
                addToHead(cur);
                if(size > n) {
                    map.remove(tail.prev.key);
                    removeNode(tail.prev);
                    size--;
                }
            }else {
                moveToHead(node);
                node.val = value;
            }
        }

        private void addToHead(Node node) {
            head.next.prev = node;
            node.next = head.next;
            head.next = node;
            node.prev = head;
        }
        private void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        private void moveToHead(Node node) {
            removeNode(node);
            addToHead(node);
        }
    }

    //前K个高频元素
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int x : nums) {
            map.put(x,map.getOrDefault(x,0)+1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((x, y)->{
            return map.get(y)-map.get(x);
        });
        for(Map.Entry entry : map.entrySet()) {
            queue.offer((Integer)entry.getKey());
        }
        int[] ret = new int[k];
        for(int i = 0; i < k; i++) {
            ret[i] = queue.poll();
        }
        return ret;
    }

    //循环汉诺塔，找规律
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long x = 0;
        long y = 0;
        long a = 0;
        long b = 0;
        for(int i = 1; i <= n; i++) {
            a = (2 * y + 1) % 1000000007;
            b = (2 * y + x + 2) % 1000000007;
            x = a;
            y = b;
        }
        System.out.println(a + " " + b);
    }
    //最长连续子序列
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int x : nums) {
            set.add(x);
        }
        int max = 0;
        for(int x : set) {
            int count = 1;
            int i = x;
            if(!set.contains(x-1)) {
                while(set.contains(i+1)) {
                    i++;
                    count++;
                }
            }

            max = Math.max(max,count);
        }
        return max;
    }
    //快速排序
    public int[] sortArray(int[] nums) {
        //快排
        quick(nums,0,nums.length-1);
        return nums;
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
    private void quick(int[] nums,int l,int r) {
        if(l >= r) {
            return;
        }
        Random random = new Random();
        int val = nums[random.nextInt(r-l+1)+l];
        int i = l;
        int left = l-1;
        int right = r+1;
        while(i < right) {
            if(nums[i] < val) {
                swap(nums,i++,++left);
            }else if(nums[i] > val){
                swap(nums,i,--right);
            }else {
                i++;
            }
        }
        quick(nums,l,left);
        quick(nums,right,r);

    }
    //归并排序
    public int[] sortArray2(int[] nums) {
        sort(nums,0,nums.length-1);
        return nums;
    }
    private void sort(int[] nums,int left,int right) {
        if(left >= right) {
            return;
        }
        int mid = (right+left)/2;
        sort(nums,left,mid);
        sort(nums,mid+1,right);
        //合并
        int k = 0;
        int[] arr = new int[right-left+1];
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        while(s1 <= e1 && s2 <= e2) {
            if(nums[s1] < nums[s2]) {
                arr[k++] = nums[s1++];
            }else {
                arr[k++] = nums[s2++];
            }
        }
        while(s1 <= e1) {
            arr[k++] = nums[s1++];
        }
        while(s2 <= e2) {
            arr[k++] = nums[s2++];
        }
        for(int i = 0; i < arr.length; i++) {
            nums[i+left] = arr[i];
        }
    }
    public int firstMissingPositive(int[] nums) {
        int i = 0;
        int n =nums.length;
        while(i < n) {
            while(nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i]) {
                //一直交换
                swap(nums,i,nums[i] -1);
            }
            i++;
        }
        for(int j = 0; j < n; j++) {
            if(nums[j] != j+1) {
                return j+1;
            }
        }
        return n+1;
    }

    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    Queue<int[]> queue = new LinkedList<>();
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ori = 0;//统计新鲜橘子的个数
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 2) {
                    queue.offer(new int[]{i,j});
                }else if(grid[i][j] == 1) {
                    ori++;
                }
            }
        }
        //出栈
        int count = 0;
        while(!queue.isEmpty() && ori > 0) {
            count++;
            int size = queue.size();
            while(size != 0) {
                int[] top = queue.poll();
                for(int i = 0; i < 4; i++) {
                    int x = top[0] + dx[i];
                    int y = top[1] + dy[i];
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        ori--;
                        queue.offer(new int[]{x,y});
                    }
                }
                size--;
            }

        }

        return ori == 0 ? count : -1;
    }
}
